export default class SortUtils {
  private static instance: SortUtils = null;

  public constructor() {}
  /**单例 */
  public static getInstance() {
    if (this.instance == null) {
      this.instance = new SortUtils();
    }
    return this.instance;
  }
  /**选择排序
   * 性质：1、时间复杂度：O(n2)  2、空间复杂度：O(1)  3、非稳定排序  4、原地排序
   */
  public selectSort(arr: number[]) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
      let min = i;
      for (let j = i + 1; j < n; j++) {
        if (arr[min] > arr[j]) min = j;
      }
      //交换
      let temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }

    return arr;
  }

  /**冒泡排序
   * 性质：1、时间复杂度：O(n2)  2、空间复杂度：O(1)  3、稳定排序  4、原地排序
   */
  public bubbleSort(arr: number[]) {
    if (arr == null || arr.length < 2) {
      return arr;
    }
    let n = arr.length;
    for (let i = 0; i < n; i++) {
      let flag = true;
      for (let j = 0; j < n - i - 1; j++) {
        if (arr[j + 1] < arr[j]) {
          flag = false;
          let t = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = t;
        }
      }

      //一趟下来是否发生位置交换
      if (flag == true) break;
    }
    console.log(arr);

    return arr;
  }

  /**	插入排序
   * 性质：1、时间复杂度：O(n2)  2、空间复杂度：O(1)  3、稳定排序  4、原地排序
   */
  public insertSort(arr: number[]) {
    if (arr == null || arr.length < 2) return arr;

    let n = arr.length;
    for (let i = 1; i < n; i++) {
      let temp = arr[i];
      let k = i - 1;
      while (k >= 0 && arr[k] > temp) k--;
      //腾出位置插进去,要插的位置是 k + 1;
      for (let j = i; j > k + 1; j--) arr[j] = arr[j - 1];
      //插进去
      arr[k + 1] = temp;
    }
    return arr;
  }

  /**测试 */
  public tset() {
    var simple = (a: number, b: number) => (a > b ? b : a);
    simple(16, 20);
    simple(10, 30);
  }
  /**
   * 加法计算 两个数都大于0
   *  @param numStr1 数1
   * @param numStr2 数2
   * @return 结果
   */
  public AddNumber(numStr1: string, numStr2: string): string {
    let numLen1: number = numStr1.length;
    let numLen2: number = numStr2.length;

    let numArray1: number[] = [];
    let numArray2: number[] = [];

    // "12345"-> [5,4,3,2,1]
    for (let i = 0; i < numLen1; i++) {
      let c: string = numStr1.substring(i, i + 1);
      numArray1[numLen1 - i - 1] = Number(c); //低位存字符串尾部数字
    }
    for (let i = 0; i < numLen2; i++) {
      let c: string = numStr2.substring(i, i + 1);
      numArray2[numLen2 - i - 1] = Number(c); //低位存字符串尾部数字
    }

    let minLen = 0; //取长度小的数位数
    let maxLen = 0; //取长度大的数位数
    let maxArray: number[] = null; //长度大的数
    if (numLen1 < numLen2) {
      minLen = numLen1;
      maxLen = numLen2;
      maxArray = numArray2;
    } else {
      minLen = numLen2;
      maxLen = numLen1;
      maxArray = numArray1;
    }

    let resultArray: number[] = []; //考虑到可能会进位，多给一个元素空间

    //两数长度相同的部分，同位相加，超出9进1
    let added = 0;
    let i = 0;
    for (; i < minLen; i++) {
      let t = numArray1[i] + numArray2[i] + added; //两数相加，再加进位
      if (t > 9) {
        added = 1; //进1
        resultArray[i] = t - 10; //当前位计算结果
      } else {
        added = 0; //不进位
        resultArray[i] = t; //当前位计算结果
      }
    }
    //长度超出部分累加
    for (; i < maxLen; i++) {
      let t = maxArray[i] + added; //多余位数加上进位
      if (t > 9) {
        added = 1; //进1
        resultArray[i] = t - 10; //当前位计算结果
      } else {
        added = 0; //不进位
        resultArray[i] = t; //当前位计算结果
      }
    }
    resultArray[i] = added; //最高位

    //拼接结果 [1,4,8,2,0] -> 2841
    let builder: number[] = [];
    for (let n = resultArray.length - 1; n >= 0; n--) {
      //如果最高位为0,移除
      if (n == resultArray.length - 1 && resultArray[resultArray.length - 1] == 0) {
        continue; //跳过
      } else {
        builder.push(resultArray[n]);
      }
    }
    let result: string = builder.toString();

    return result.replace(/,/g, "");
  }

  /**
   * 两数相减 两个数都大于0
   * @param numStr1 数1
   * @param numStr2 数2
   * @return 结果
   */
  public subtract(numStr1: string, numStr2: string): string {
    let numLen1 = numStr1.length;
    let numLen2 = numStr2.length;

    let numArray1: number[] = [];
    let numArray2: number[] = [];

    // "12345"-> [5,4,3,2,1]
    for (let i = 0; i < numLen1; i++) {
      let c: string = numStr1.substring(i, i + 1);
      numArray1[numLen1 - i - 1] = Number(c); //低位存字符串尾部数字
    }

    for (let i = 0; i < numLen2; i++) {
      let c: string = numStr2.substring(i, i + 1);
      numArray2[numLen2 - i - 1] = Number(c); //低位存字符串尾部数字
    }

    let minLen = 0; //取长度小的数位数
    let maxLen = 0; //取长度大的数位数
    let maxArray: number[] = null; //数值大的数
    if (numLen1 < numLen2) {
      minLen = numLen1;
      maxLen = numLen2;
      maxArray = numArray2;
    } else {
      minLen = numLen2;
      maxLen = numLen1;
      maxArray = numArray1;
      if (numLen1 == numLen2) {
        //等于
        if (
          this.getMax(Number(numArray1.toString().replace(/,/g, "")), Number(numArray2.toString().replace(/,/g, ""))) ==
          Number(numArray1.toString().replace(/,/g, ""))
        ) {
          maxArray = numArray1;
        } else {
          maxArray = numArray2;
        }
      }
    }
    let minArray: number[] = maxArray == numArray1 ? numArray2 : numArray1; //数值小的数

    let resultArray: number[] = [];

    //大数-小数，同位相减，小于0借位
    let subtracted = 0;
    let i = 0;
    for (; i < minLen; i++) {
      let t = maxArray[i] - minArray[i] - subtracted; //两数相减，再减借位
      if (t < 0) {
        subtracted = 1; //向高位借1，暂存起来
        resultArray[i] = t + 10; //当前位计算结果（借1相当于借了10）
      } else {
        subtracted = 0; //不借位
        resultArray[i] = t; //当前位计算结果
      }
    }
    //大数超出部分减掉借位
    for (; i < maxLen; i++) {
      let t = maxArray[i] - subtracted; //多余位数减掉借位
      if (t < 0) {
        subtracted = 1; //进1
        resultArray[i] = t + 10; //当前位计算结果
      } else {
        subtracted = 0; //不借位
        resultArray[i] = t; //当前位计算结果
      }
    }

    //拼接结果 [1,4,8,2,0] -> 2841
    let builder: number[] = [];
    let highBitNotEqualZero = false; //存在高位不为0的情况，低位0保留
    for (let n = resultArray.length - 1; n >= 0; n--) {
      //如果高位为0,移除
      if (resultArray[n] == 0 && !highBitNotEqualZero && n != 0) {
        //高位无用的0去除
        continue; //跳过
      } else {
        highBitNotEqualZero = true; //找到不为0的位
        builder.push(resultArray[n]);
      }
    }

    if (maxArray == numArray1) {
      //第一个数大或相等
    } else {
      //第一个数小于第二个数，相减为负数
      let result: string = "-" + builder.toString();
      return result.replace(/,/g, "");
    }
    let result: string = builder.toString();
    return result.replace(/,/g, "");
  }

  public getMax(a: number, b: number): number {
    if (a <= b) {
      return b;
    }
    return a;
  }

  /**
   * 两数相乘
   * @param numStr1 数1
   * @param numStr2 数2
   * @return 结果
   */
  public bigNumberMultiply2(num1, num2): string {
    num1 = toStringArray(num1);
    num2 = toStringArray(num2);
    let result = [];

    // 乘数，假如为11
    for (let i = 0; i < num1.length; i++) {
      // 被乘数，假如为111，如将11的1与111的每一位相乘然后存入
      for (let j = 0; j < num2.length; j++) {
        // 将结果添加到对应的位数上，如果该位数上存在则继续加，不存在则写入
        result[i + j] = result[i + j] ? result[i + j] + num1[i] * num2[j] : num1[i] * num2[j];
      }
    }

    for (let i = 0; i < result.length; i++) {
      // 确认是否进位，仅在进位时增加数组长度
      let carry = Math.floor(result[i] / 10);

      if (carry) {
        result[i + 1] = result[i + 1] ? result[i + 1] + carry : carry;
      }

      result[i] = result[i] % 10;
    }

    return result.reverse().join("");

    function toStringArray(num) {
      return String(num).split("").reverse();
    }
  }
  /**
   * 两数相除
   */
  public division(a, b) {
    var alen = a.length,
      blen = b.length;
    var quotient = 0,
      remainder = 0;
    var result = [],
      temp = 0;
    for (var i = 0; i < alen; i++) {
      temp = remainder * 10 + parseInt(a[i]);
      if (temp < b) {
        remainder = temp;
        result.push(0);
      } else {
        quotient = parseInt(String(temp / b));
        remainder = temp % b;
        result.push(quotient);
      }
    }
    return [result.join("").replace(/\b(0+)/gi, ""), remainder]; //结果返回[商，余数]
  }
}
